package chapter5_stack_and_linked;

import java.util.*;

/**
 * @author yuh
 * @date 2018/4/12 13:50
 * @description 最大的K个元素 jdk默认是小根堆
 */
public class TopKElements {

    static <T extends Comparable> List<T> getTopK(T[] arr, int k) {
        Map<T, Integer> map = new HashMap<>();
        for (T t : arr) {
            Integer count = map.get(t);
            if (count == null) {
                map.put(t, 1);
            } else {
                map.put(t, count + 1);
            }
        }
        PriorityQueue<TwoTupleCompare<T, Integer>> queue = new PriorityQueue<>();
        Set<Map.Entry<T, Integer>> entries = map.entrySet();
        for (Map.Entry<T, Integer> entry : entries) {
            TwoTupleCompare<T, Integer> compare = new TwoTupleCompare<>(entry.getKey(), entry.getValue());
            queue.offer(compare);
        }
        LinkedList<T> linkedList = new LinkedList<>();
        for (int i = 0; i < k; i++) {
            linkedList.add(queue.poll().a);
        }
        return linkedList;
    }

    public static void main(String[] args) {
        Integer[] arr = new Integer[]{1,2,3,4,5,6,7,2,3,4,5};
        System.out.println(getTopK(arr,3));
    }
}
